'''
解题思路（参考网上已理解）
1.从矩阵可以看出：每行最左边的元素都是该行最小的，同时它的下方和右方又都比他大。
因此：矩阵左下角的元素，所有比他大的元素都在他右侧（所在列右侧），所有比他小的元素都在他上侧（所在行上侧）。
2.所以可以用最后一行最左边的元素作为起始索引（i，j）。
若是索引值大于target，说明target可能再索引所在行的上方，i-=1；若是索引值小于target，说明target可能在索引所在列的右方，j+=1；若是恰好是该值，则输出。
'''

matrix = [[1, 4, 7, 11, 15],[2, 5, 8, 12, 19],[3, 6, 9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30]]
target = input("请输入目标值： ")
class Solution:
    def searchMatrix(self, matrix,target):
        if not matrix:
            return False
        rol = len(matrix)
        col = len(matrix[0])
        i = rol - 1
        j = 0
        judge = False
        while (i >= 0) or (j < col):
            if i < 0 or j > (col - 1):
                break
            if matrix[i][j] > target:
                i = i -1
            elif matrix[i][j] > target:
                j = j+1
            elif matrix[i][j] == target:
                judge = True
                break
        return judge
